import java.util.HashMap;
import java.util.Map;

public class Leetcode {
}
//leetcode:面试题01.01.判定字符是否唯一
class Solution1 {
    public boolean isUnique(String astr) {
        int ret = 0;
        for(int i = 0;i < astr.length();i++){
            int x = astr.charAt(i)-'a';
            if((ret & (1<<x)) != 0) return false;
            else ret |= (1<<x);
        }
        return true;
    }
}


//leetcode:268:丢失的数字
class Solution2 {
    public int missingNumber(int[] nums) {
        int ret = 0;
        for(int x : nums){
            ret ^= x;
        }
        for(int i= 0;i <= nums.length;i++){
            ret ^= i;
        }
        return ret;
    }
}

//leetcode:371:两整数之和
class Solution3 {
    public int getSum(int a, int b) {
        while(b != 0){
            int x = (a & b)<<1;
            a = (a ^ b);
            b = x;
        }
        return a;
    }
}

//leetcode:137:只出现一次的数字II
class Solution4 {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0;i < 32 ;i++){
            int sum = 0;
            for(int x : nums){
                if(((x>>i)&1) == 1) sum++;
            }
            sum %= 3;
            if(sum == 1) ret |= 1<<i;
        }
        return ret;
    }
}

//leetcode:260:只出现一次的数字III
class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int[] arr = new int[2];
        int index = 0;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() == 1){
                arr[index++] = entry.getKey();
            }
        }
        return arr;
    }
}

//leetcode:面试题17.19.消失的两个数字
//丢失的数字+只出现一次的数字III
class Solution5 {
    public int[] missingTwo(int[] nums) {
        //异或所有的元素，找到缺失的数字
        int tmp = 0;
        for(int x : nums){
            tmp ^= x;
        }
        for(int i = 1;i <= nums.length+2;i++){
            tmp ^= i;
        }
        //将两个缺失的元素分开
        //去找两元素后比特位不等的位置，即异或后的tmp为比特位为1的位置
        //从0开始找遇到1就结束循环，此时diff就是不等的位置，不等于1就diff++往下找
        int diff = 0;
        while(true){
            if(((tmp >> diff)&1) == 1) break;
            else diff++;
        }
        //创建一个数组用来存储缺失的元素
        int[] arr = new int[2];
        //按照我们diff位置比特位的不同分成两类异或：等于1的异或，等于0的异或
        //根据diff位置比特位的不同再次对所有的元素按照这两类异或
        //比特位为1的异或放到下标为1的数组中
        //比特位为0的异或放到下标为0的数组中
        for(int x : nums){
            if(((x >> diff) &1) == 1) arr[0] ^= x;
            else arr[1] ^= x;
        }

        for(int i = 1;i <= nums.length+2;i++){
            if(((i >> diff) &1) == 1) arr[0] ^= i;
            else arr[1] ^= i;
        }
        //最后返回这个数组
        return arr;
    }
}